SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Berlekamp–Welch algorithm</title>

</head>

Berlekamp–Welch algorithm

</h1>

</header>

The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for <a href="Elwyn_R._Berlekamp" class="mw-redirect" title="Elwyn R. Berlekamp">Elwyn R. Berlekamp</a> and <a href="Lloyd_R._Welch" title="Lloyd R. Welch">Lloyd R. Welch</a>. This is a decoder algorithm that efficiently corrects errors in <a href="Reed%E2%80%93Solomon_error_correction" title="Reed–Solomon error correction">Reed–Solomon codes</a> for an RS(n, k), code based on the Reed Solomon original view where a message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1},\cdots ,m_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1},\cdots ,m_{k}}</annotation>

</semantics>

</math><img src="./bf8db3abca3dd0274faf17f59383dc54b4ab774b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.402ex; height:2.009ex;" alt="{\displaystyle m_{1},\cdots ,m_{k}}" loading="lazy"> is used as coefficients of a polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a_{i})}</annotation>

</semantics>

</math><img src="./f297681610b244d158ab4cfdcbb786b42c203317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.58ex; height:2.843ex;" alt="{\displaystyle F(a_{i})}" loading="lazy"> or used with <a href="Lagrange_polynomial" title="Lagrange polynomial">Lagrange interpolation</a> to generate the polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a_{i})}</annotation>

</semantics>

</math><img src="./f297681610b244d158ab4cfdcbb786b42c203317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.58ex; height:2.843ex;" alt="{\displaystyle F(a_{i})}" loading="lazy"> of degree < k for inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},\cdots ,a_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1},\cdots ,a_{k}}</annotation>

</semantics>

</math><img src="./a878994eb57743eeaaf87ed487ad9e79a2c235d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.781ex; height:2.009ex;" alt="{\displaystyle a_{1},\cdots ,a_{k}}" loading="lazy"> and then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a_{i})}</annotation>

</semantics>

</math><img src="./f297681610b244d158ab4cfdcbb786b42c203317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.58ex; height:2.843ex;" alt="{\displaystyle F(a_{i})}" loading="lazy"> is applied to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{k+1},\cdots ,a_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{k+1},\cdots ,a_{n}}</annotation>

</semantics>

</math><img src="./2879d873cdcfeaa1de166a3f9e528b071d110481.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.046ex; height:2.009ex;" alt="{\displaystyle a_{k+1},\cdots ,a_{n}}" loading="lazy"> to create an encoded codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1},\cdots ,c_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1},\cdots ,c_{n}}</annotation>

</semantics>

</math><img src="./12014b5d4bb6f277727beb93e0630ba913bc7411.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.465ex; height:2.009ex;" alt="{\displaystyle c_{1},\cdots ,c_{n}}" loading="lazy">.

The goal of the decoder is to recover the original encoding polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a_{i})}</annotation>

</semantics>

</math><img src="./f297681610b244d158ab4cfdcbb786b42c203317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.58ex; height:2.843ex;" alt="{\displaystyle F(a_{i})}" loading="lazy">, using the known inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},\cdots ,a_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1},\cdots ,a_{n}}</annotation>

</semantics>

</math><img src="./c28b1cd802d561192128b323b66e46a1fb5e3b67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.911ex; height:2.009ex;" alt="{\displaystyle a_{1},\cdots ,a_{n}}" loading="lazy"> and received codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{1},\cdots ,b_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{1},\cdots ,b_{n}}</annotation>

</semantics>

</math><img src="./3c06e89e53f94e9150840c438462ae4413e41891.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.446ex; height:2.509ex;" alt="{\displaystyle b_{1},\cdots ,b_{n}}" loading="lazy"> with possible errors. It also computes an error polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(a_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(a_{i})}</annotation>

</semantics>

</math><img src="./7e2efbc7bd2209a4901adcedd04950711a879e72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.614ex; height:2.843ex;" alt="{\displaystyle E(a_{i})}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(a_{i})=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(a_{i})=0}</annotation>

</semantics>

</math><img src="./4ffdedcceb82038e7718ca8d5290c2ba1ffba547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.875ex; height:2.843ex;" alt="{\displaystyle E(a_{i})=0}" loading="lazy"> corresponding to errors in the received codeword.

<div class="mw-heading mw-heading2"><h2 id="The_key_equations">The key equations</h2></div>

Defining e = number of errors, the key set of n equations is

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}E(a_{i})=E(a_{i})F(a_{i})}</annotation>

</semantics>

</math><img src="./88ef8b411ebd5dc4f7cffce673df04dcfa1be951.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.704ex; height:2.843ex;" alt="{\displaystyle b_{i}E(a_{i})=E(a_{i})F(a_{i})}" loading="lazy"></dd></dl>

Where E(ai) = 0 for the e cases when bi ≠ F(ai), and E(ai) ≠ 0 for the n - e non error cases where bi = F(ai) . These equations can't be solved directly, but by defining Q() as the product of E() and F():

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(a_{i})=E(a_{i})F(a_{i})}</annotation>

</semantics>

</math><img src="./29438909afeb54da392ac9b1bab50bfc74190665.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.97ex; height:2.843ex;" alt="{\displaystyle Q(a_{i})=E(a_{i})F(a_{i})}" loading="lazy"></dd></dl>

and adding the constraint that the most significant coefficient of E(ai) = ee = 1, the result will lead to a set of equations that can be solved with linear algebra.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}E(a_{i})=Q(a_{i})}</annotation>

</semantics>

</math><img src="./fb6a03a1de824000aca75d0b13a44b6208dbfdb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.187ex; height:2.843ex;" alt="{\displaystyle b_{i}E(a_{i})=Q(a_{i})}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}</annotation>

</semantics>

</math><img src="./e4f7583303f463a97cf6fb5cf644b86c35699ca9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.19ex; height:2.843ex;" alt="{\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e}a_{i}^{e})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=0}</annotation>

</semantics>

</math><img src="./3428095cf42897999cdad5f2188d0dc11119911f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:70.555ex; height:3.176ex;" alt="{\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e}a_{i}^{e})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=0}" loading="lazy"></dd></dl>

where q = n - e - 1. Since ee is constrained to be 1, the equations become:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e-1}a_{i}^{e-1})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=-b_{i}a_{i}^{e}}</annotation>

</semantics>

</math><img src="./04ff7ba2b303ee9a04b2ef7085bf716888813142.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:79.427ex; height:3.343ex;" alt="{\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e-1}a_{i}^{e-1})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=-b_{i}a_{i}^{e}}" loading="lazy"></dd></dl>

resulting in a set of equations which can be solved using linear algebra, with time complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>

</semantics>

</math><img src="./6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy">.

The algorithm begins assuming the maximum number of errors e = ⌊(n-k)/2⌋. If the equations can not be solved (due to redundancy), e is reduced by 1 and the process repeated, until the equations can be solved or e is reduced to 0, indicating no errors. If Q()/E() has remainder = 0, then F() = Q()/E() and the code word values F(ai) are calculated for the locations where E(ai) = 0 to recover the original code word. If the remainder ≠ 0, then an uncorrectable error has been detected.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Consider RS(7,3) (n = 7, k = 3) defined in GF(7) with α = 3 and input values: ai = i-1 : {0,1,2,3,4,5,6}. The message to be systematically encoded is {1,6,3}. Using Lagrange interpolation, F(ai) = 3 x2 + 2 x + 1, and applying F(ai) for a4 = 3 to a7 = 6, results in the code word {1,6,3,6,1,2,2}. Assume errors occur at c2 and c5 resulting in the received code word {1,5,3,6,3,2,2}. Start off with e = 2 and solve the linear equations:

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}b_{1}&b_{1}a_{1}&-1&-a_{1}&-a_{1}^{2}&-a_{1}^{3}&-a_{1}^{4}\\b_{2}&b_{2}a_{2}&-1&-a_{2}&-a_{2}^{2}&-a_{2}^{3}&-a_{2}^{4}\\b_{3}&b_{3}a_{3}&-1&-a_{3}&-a_{3}^{2}&-a_{3}^{3}&-a_{3}^{4}\\b_{4}&b_{4}a_{4}&-1&-a_{4}&-a_{4}^{2}&-a_{4}^{3}&-a_{4}^{4}\\b_{5}&b_{5}a_{5}&-1&-a_{5}&-a_{5}^{2}&-a_{5}^{3}&-a_{5}^{4}\\b_{6}&b_{6}a_{6}&-1&-a_{6}&-a_{6}^{2}&-a_{6}^{3}&-a_{6}^{4}\\b_{7}&b_{7}a_{7}&-1&-a_{7}&-a_{7}^{2}&-a_{7}^{3}&-a_{7}^{4}\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}-b_{1}a_{1}^{2}\\-b_{2}a_{2}^{2}\\-b_{3}a_{3}^{2}\\-b_{4}a_{4}^{2}\\-b_{5}a_{5}^{2}\\-b_{6}a_{6}^{2}\\-b_{7}a_{7}^{2}\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./be119109025b77ebd6e58f8f545acc99a682f34c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -11.838ex; width:62.693ex; height:24.843ex;" alt="{\displaystyle {\begin{bmatrix}b_{1}&b_{1}a_{1}&-1&-a_{1}&-a_{1}^{2}&-a_{1}^{3}&-a_{1}^{4}\\b_{2}&b_{2}a_{2}&-1&-a_{2}&-a_{2}^{2}&-a_{2}^{3}&-a_{2}^{4}\\b_{3}&b_{3}a_{3}&-1&-a_{3}&-a_{3}^{2}&-a_{3}^{3}&-a_{3}^{4}\\b_{4}&b_{4}a_{4}&-1&-a_{4}&-a_{4}^{2}&-a_{4}^{3}&-a_{4}^{4}\\b_{5}&b_{5}a_{5}&-1&-a_{5}&-a_{5}^{2}&-a_{5}^{3}&-a_{5}^{4}\\b_{6}&b_{6}a_{6}&-1&-a_{6}&-a_{6}^{2}&-a_{6}^{3}&-a_{6}^{4}\\b_{7}&b_{7}a_{7}&-1&-a_{7}&-a_{7}^{2}&-a_{7}^{3}&-a_{7}^{4}\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}-b_{1}a_{1}^{2}\\-b_{2}a_{2}^{2}\\-b_{3}a_{3}^{2}\\-b_{4}a_{4}^{2}\\-b_{5}a_{5}^{2}\\-b_{6}a_{6}^{2}\\-b_{7}a_{7}^{2}\\\end{bmatrix}}}" loading="lazy"></dd></dl>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&0&6&0&0&0&0\\5&5&6&6&6&6&6\\3&6&6&5&3&6&5\\6&4&6&4&5&1&3\\3&5&6&3&5&6&3\\2&3&6&2&3&1&5\\2&5&6&1&6&1&6\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}0\\2\\2\\2\\1\\6\\5\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./4e271c3270a8a1ea3f96bc5119f7360edea083a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:40.122ex; height:22.343ex;" alt="{\displaystyle {\begin{bmatrix}1&0&6&0&0&0&0\\5&5&6&6&6&6&6\\3&6&6&5&3&6&5\\6&4&6&4&5&1&3\\3&5&6&3&5&6&3\\2&3&6&2&3&1&5\\2&5&6&1&6&1&6\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}0\\2\\2\\2\\1\\6\\5\\\end{bmatrix}}}" loading="lazy"></dd></dl>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}4\\2\\4\\3\\3\\1\\3\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./cd48e95d13becb7510b6dc7079290e08a033042b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:40.122ex; height:22.343ex;" alt="{\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}4\\2\\4\\3\\3\\1\\3\\\end{bmatrix}}}" loading="lazy"></dd></dl>

Starting from the bottom of the right matrix, and the constraint e2 = 1:

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(a_{i})=3x^{4}+1x^{3}+3x^{2}+3x+4}</annotation>

</semantics>

</math><img src="./28aebea067308d627dd174a178175071da202149.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.431ex; height:3.176ex;" alt="{\displaystyle Q(a_{i})=3x^{4}+1x^{3}+3x^{2}+3x+4}" loading="lazy">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(a_{i})=1x^{2}+2x+4}</annotation>

</semantics>

</math><img src="./f35ef316e6ccd86d24d8b43eb0117efebace3ed3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.595ex; height:3.176ex;" alt="{\displaystyle E(a_{i})=1x^{2}+2x+4}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a_{i})=Q(a_{i})/E(a_{i})=3x^{2}+2x+1}</annotation>

</semantics>

</math><img src="./17d00d46c5f74bbd0a0cb446ad80c8399f1eda84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:37.112ex; height:3.176ex;" alt="{\displaystyle F(a_{i})=Q(a_{i})/E(a_{i})=3x^{2}+2x+1}" loading="lazy"> with remainder = 0.

E(ai) = 0 at a2 = 1 and a5 = 4

Calculate F(a2 = 1) = 6 and F(a5 = 4) = 1 to produce corrected code word {1,6,3,6,1,2,2}.

<ul><li><a href="Reed%E2%80%93Solomon_error_correction" title="Reed–Solomon error correction">Reed–Solomon error correction</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://people.csail.mit.edu/madhu/FT02/">MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html">University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra</a></li>

<li>Algebraic Codes on Lines, Planes and Curves, An Engineering Approach – Richard E. Blahut</li>

<li>Welch Berlekamp Decoding of Reed–Solomon Codes – L. R. Welch</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output .citation{word-wrap:break-word}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}

/* end https://en.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://worldwide.espacenet.com/textdoc?DB=EPODOC&IDX=US4,633,470">US 4,633,470</a>, <a href="Lloyd_R._Welch" title="Lloyd R. Welch">Welch, Lloyd R.</a> & <a href="Elwyn_Berlekamp" title="Elwyn Berlekamp">Berlekamp, Elwyn R.</a>, "Error Correction for Algebraic Block Codes", published September 27, 1983, issued December 30, 1986<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Apatent&rft.number=4,633,470&rft.cc=US&rft.title=Error+Correction+for+Algebraic+Block+Codes&rft.inventor=Welch&rft.date=December 30, 1986&rft.pubdate=September 27, 1983">  – The patent by Lloyd R. Welch and Elewyn R. Berlekamp</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-10-29" href="https://en.wikipedia.org/wiki/?title=Berlekamp%E2%80%93Welch_algorithm&oldid=1182501340">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>